import java.util.*;

/**
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 *
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isMatch("aa", "a"));//false
        System.out.println(solution.isMatch("a", ".*..a*"));//false
        System.out.println(solution.isMatch("a", ".*.."));//false
        System.out.println(solution.isMatch("ab", ".*c")); //false
        System.out.println(solution.isMatch("ccbbabbbabababa", ".*.ba*c*c*aab.a*b*"));
        System.out.println("------------");
        System.out.println(solution.isMatch("abc", ".*")); //true
        System.out.println(solution.isMatch("aaa", "a*a"));//true
        System.out.println(solution.isMatch("aaa", "ab*a*c*a"));//true
        System.out.println(solution.isMatch("ab", ".*.."));
        System.out.println(solution.isMatch("abcdede", "ab.*de"));
        System.out.println(solution.isMatch("aaa", "ab*ac*a"));
        System.out.println(solution.isMatch("cabbbbcbcacbabc", ".*b.*.ab*.*b*a*c"));
    }

    private int endIndex;
    private char[] content;

    public boolean isMatch(String s, String p) {
        Pattern[] patternArr = parse(p);

        content = s.toCharArray();
        endIndex = content.length - 1;

        int last = 0;
        for (Pattern pattern : patternArr) {
            if (!pattern.match()) {
                return false;
            }
            if (pattern.end > 0) {
                last = pattern.end;
            }
        }

        return last == content.length - 1;
    }

    public Pattern[] parse(String rule) {
        char[] chars = rule.toCharArray();

        int count = 0;
        for (char c : chars) {
            if (c == '*') {
                count++;
            }
        }

        Pattern[] arr = new Pattern[chars.length - count];

        Pattern NULL = new Pattern();
        NULL.fixed = true;
        NULL.start = -1;
        NULL.end = -1;

        int cur = 0;
        int i = 0;
        while (i < chars.length) {
            Pattern p = new Solution.Pattern();
            p.code = chars[i];
            if ((i + 1) < chars.length && chars[i + 1] == '*') {
                p.multiple = true;
                i++;
            }
            if (cur == 0) {
                p.pre = NULL;
            } else {
                p.pre = arr[cur - 1];
            }

            arr[cur] = p;
            i++;
            cur++;
        }

        return arr;
    }

    private class Pattern {
        private char code;
        private boolean multiple = false;
        private int start = -1;
        private int end = -1;
        private boolean fixed = false;
        private Pattern pre;

        private boolean match() {
            while (!find()) {
                if (!pre.forward(code)) {
                    return false;
                }
            }
            return true;
        }

        private boolean find() {
            //起始位置
            int cur = getLast() + 1;

            //查找
            if (code == '.') {
                if (multiple) {
                    if (cur > endIndex) {
                        start = -1;
                        end = -1;
                    } else {
                        start = cur;
                        end = endIndex;
                    }
                } else {
                    if (cur > endIndex) {
                        return false;
                    } else {
                        start = cur;
                        end = cur;
                    }
                }
            } else {
                if (multiple) {
                    if (cur > endIndex) {
                        start = -1;
                        end = -1;
                    } else {
                        int count = 0;
                        while (cur <= endIndex) {
                            if (content[cur] == code) {
                                count++;
                                cur++;
                            } else {
                                break;
                            }
                        }
                        if (count > 0) {
                            start = cur - count;
                            end = cur - 1;
                        } else {
                            start = -1;
                            end = -1;
                        }
                    }
                } else {
                    if (cur > endIndex) {
                        return false;
                    }
                    if (content[cur] == code) {
                        start = cur;
                        end = cur;
                    } else {
                        return false;
                    }
                }
            }

            if (multiple) {
                if (start == -1) {
                    fixed = pre.fixed;
                } else {
                    fixed = false;
                }
            } else {
                fixed = pre.fixed;
            }

            return true;
        }

        private boolean forward(char findCode) {
            if (fixed) {
                return false;
            }
            //从自己处分字符
            if (splitSelf(findCode)) {
                return true;
            }

            //从上级获取
            char newCode = code;
            if (multiple) {
                newCode = findCode;
            } else if (code == '.' && content[start] != findCode) {
                newCode = findCode;
            }

            while (pre.forward(newCode)) {
                if (find()) {
                    return true;
                }
            }

            return false;
        }

        private boolean splitSelf(char findCode) {
            boolean find = false;
            if (start > -1 && multiple) {
                if (findCode == '.') {
                    find = true;
                    end--;
                } else {
                    while (end >= start) {
                        if (content[end] == findCode) {
                            end--;
                            find = true;
                            break;
                        }
                        end--;
                    }
                }
                if (end < start) {
                    start = -1;
                    end = -1;
                    fixed = pre.fixed;
                }
                return find;
            }
            return false;
        }

        private int getLast() {
            if (Objects.isNull(pre)) {
                return -1;
            }
            if (pre.end < 0) {
                return pre.getLast();
            } else {
                return pre.end;
            }
        }

    }

}